Disjoint Paths in Decomposable Digraphs

The k‐linkage problem is as follows: given a digraph and a collection of k terminal pairs such that all these vertices are distinct; decide whether D has a collection of vertex disjoint paths such that is from to for . A digraph is k‐linked if it has a k‐linkage for every choice of 2k distinct vertices and every choice of k pairs as above. The k‐linkage problem is NP‐complete already for [11] and there exists no function such that every ‐strong digraph has a k‐linkage for every choice of 2k distinct vertices of D [17]. Recently, Chudnovsky et al. [9] gave a polynomial algorithm for the k‐linkage problem for any fixed k in (a generalization of) semicomplete multipartite digraphs. In this article, we use their result as well as the classical polynomial algorithm for the case of acyclic digraphs by Fortune et al. [11] to develop polynomial algorithms for the k‐linkage problem in locally semicomplete digraphs and several classes of decomposable digraphs, including quasi‐transitive digraphs and directed cographs. We also prove that the necessary condition of being ‐strong is also sufficient for round‐decomposable digraphs to be k‐linked, obtaining thus a best possible bound that improves a previous one of . Finally we settle a conjecture from [3] by proving that every 5‐strong locally semicomplete digraph is 2‐linked. This bound is also best possible (already for tournaments) [1].     

Global X2A′ potential energy surface of Li2H and quantum dynamics of H + Li2 (X1Σg+) → Li + LiH (X1Σ+) reaction

A global potential energy surface (PES) for the electronic ground state of Li₂H system is constructed over a large configuration space. About 30 000 ab initio energy points have been calculated by MRCI‐F12 method with aug‐cc‐pVTZ basis set. The neural network method is applied to fit the PES and the root mean square error of the current PES is only 1.296 meV. The reaction dynamics of the title reaction has been carried out by employing time‐dependent wave packet approach with second order split operator on the new PES. The reaction probability, integral cross section and thermal rate constant are obtained from the dynamics calculation. In most of the collision energy regions, the integral cross sections are in well agreement with the results reported by Gao et al. The rate constant calculated from the new PES increases in the temperature range of present investigation.     

On Vaporizing Water Flow in Hot Sub-Vertical Rock Fractures

Water injection into unsaturated fractured rock at above-boiling temperatures gives rise to complex fluid flow and heat transfer processes. Examples include water injection into depleted vapor-dominated geothermal reservoirs, and emplacement of heat-generating nuclear wastes in unsaturated fractured rock. We conceptualize fractures as two-dimensional heterogeneous porous media, and use geostatistical techniques to generate synthetic permeability distributions in the fracture plane. Water flow in hot high-angle fractures is simulated numerically, taking into account the combined action of gravity, capillary, and pressure forces, and conductive heat transfer from the wall rocks which gives rise to strong vaporization. In heterogeneous fractures boiling plumes are found to have dendritic shapes, and to be subject to strong lateral flow effects. Fractures with spatially-averaged homogeneous permeabilities tend to give poor approximations for vaporization behavior and liquid migration patterns. Depending on water flow rates, rock temperature, and fracture permeability, liquid water can migrate considerable distances through fractured rock that is at above-boiling temperatures and be only partially vaporized.     

EXPERIMENTAL RESEARCH ON FAILURE AND ENERGY DISSIPATION CHRACTERISTICS OF THE SANDSTONE1)

通过三轴卸荷试验,探究了不同路径下卸荷速率对砂岩力学特性及破坏过程中的能量耗散的影响。试验结果表明在全过程应力-应变曲线的弹性阶段,轴向变形起主导作用,弹塑性阶段,环向应变的增加值大于轴向应变增加值。在围压卸荷阶段,卸荷速率越小,卸荷阶段的应变折合柔度越大,此时岩样的变形不充分,呈现明显的脆性破坏。恒主应力差路径下的耗散能大于恒轴压路径下的耗散能的35%,卸荷速率越大,岩样的弹性应变能越小。     

Kernels by monochromatic paths in digraphs with covering number 2

We call the digraph D an k-colored digraph if the arcs of D are colored with k colors. A subdigraph H of D is called monochromatic if all of its arcs are colored alike. A set N⊆V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u,v∈N, there is no monochromatic directed path between them, and (ii) for every vertex x∈(V(D)?N), there is a vertex y∈N such that there is an xy-monochromatic directed path. In this paper, we prove that if D is an k-colored digraph that can be partitioned into two vertex-disjoint transitive tournaments such that every directed cycle of length 3,4 or 5 is monochromatic, then D has a kernel by monochromatic paths. This result gives a positive answer (for this family of digraphs) of the following question, which has motivated many results in monochromatic kernel theory: Is there a natural numberlsuch that if a digraphDisk-colored so that every directed cycle of length at mostlis monochromatic, thenDhas a kernel by monochromatic paths?     

会议选址问题的优化模型

国内某公司在各省会城市都设有分支机构,公司每年都有频繁的会议和培训工作需要各地分支机构派人参加,如何在大陆地区31个省会城市里选择一个城市作为会议地址,使得举办会议的成本最低且中转次数最少.建立了该会议选址问题的双目标优化模型,收集处理了有关实际数据,利用网络最短路算法和约束法等得到了该会议选址问题的解.在不考虑中转费用的情况下,得出成本最低且中转次数最少的会议地址是西安;在考虑中转费用的情况下,根据中转费用的不同给出了可供实际决策的最优会议选址方案.     

A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries,Selective Pickups and Time Windows

In the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows, the set of customers is the union of delivery customers and pickup customers. A fleet of identical capacitated vehicles based at the depot must perform all deliveries and profitable pickups while respecting time windows. The objective is to minimize routing costs, minus the revenue associated with the pickups. Five variants of the problem are considered according to the order imposed on deliveries and pickups. An exact branch-and-price algorithm is developed for the problem. Computational results are reported for instances containing up to 100 customers.